package com.atcumt.Carl.Greedy;

import java.util.Arrays;

public class Greedy01 {

    /**
     * 柠檬水找零
     */
    public boolean lemonadeChange(int[] bills) {

        int cash_5 = 0;
        int cash_10 = 0;

        for (int i = 0; i < bills.length; i++) {
            if (bills[i] == 5) {
                cash_5++;
            } else if (bills[i] == 10) {
                cash_10++;
                cash_5--;
            } else {
                if (cash_10 > 0) {
                    cash_10--;
                    cash_5--;
                } else {
                    cash_5 -= 3;
                }
            }
            if (cash_5 < 0 || cash_10 < 10) {
                return false;
            }
        }
        return true;
    }

    /**
     * 分发饼干
     * 大饼干喂胃口大的孩子
     */
    public int findContentChildren(int[] g, int[] s) {

        Arrays.sort(g);
        Arrays.sort(s);
        int count = 0; // 记录喂饱的小孩数
        int start = g.length; // 指向饼干

        for (int i = 0; i < s.length; i++) {
            if (start >= 0 && s[start] >= g[i]) {
                count++;
                start--;
            }
        }
        return count;
    }

    /**
     * 摆动序列
     */
    public int wiggleMaxLength(int[] nums) {
        if (nums.length < 2) {
            return nums.length;
        }

        int preDiff = nums[1] - nums[0]; // 之前的差值
        int res = nums[1] == nums[0] ? 1 : 2;

        for (int i = 2; i < nums.length; i++) {
            int curDiff = nums[i] - nums[i - 1]; // 当前差值
            if (curDiff > 0 && preDiff <= 0 || curDiff < 0 && preDiff >= 0) {
                res++;
                preDiff = curDiff;
            }
        }
        return res;
    }

    /**
     * 跳跃游戏
     * 核心：找最大覆盖范围
     */
    public boolean canJump(int[] nums) {
        if (nums.length < 2) {
            return true;
        }

        int cover = 0;
        for (int i = 0; i <= cover; i++) {
            cover = Math.max(cover, i + nums[i]);
            if (cover >= nums.length - 1) {
                return true;
            }
        }
        return false;
    }

    /**
     * 跳跃游戏Ⅱ: 求最少跳跃次数
     */
    public int jump(int[] nums) {
        int cover = 0;
        int count = 0;
        int end = 0; // 判断当前这一步能否到达最远位置 k
        for (int i = 0; i < nums.length; i++) {
            cover = Math.max(cover, i + nums[i]);

            // 遇到跳跃边界，更新边界和跳跃次数
            if (end == i) {
                end = cover;
                count++;
            }
        }
        return count;
    }

    /**
     * 最少数量的箭引爆气球
     * 排序 + 贪心
     */
    public int findMinArrowShots(int[][] points) {
        if (points.length == 0) {
            return 0;
        }

        Arrays.sort(points, (o1, o2) -> Integer.compare(o1[1], o2[1])); // 按右边界排序
        int count = 1;
        int right = points[0][1];
        for (int i = 1; i < points.length; i++) {
            if (right < points[i][0]) {
                count++;
                right = points[i][1];
            }
        }
        return count;
    }

}
